《剑指offer》 03.数组中重复的数组

剑指offer
留言

题目描述

找出数组中重复的数字。

在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。

示例 1：

输入：

[2, 3, 1, 0, 2, 5, 3]

输出：2 或 3

限制：

2 <= n <= 100000

解法一：hash表

思路

最简单直接的想法就是hash表：一个空白数组，数组中的元素作为空白元素的下标，进行加一操作，一但某个空白元素中的某个元素在加一操作前已经不为0，那么就找到了一个重复的元素，直接返回就好。

代码

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int findRepeatNumber(vector<int>& nums) {
        vector<int> hash(100000);
        for(auto n : nums){
            if(hash[n]!=0)
                return n;
            hash[n]++;
        }
        return -1;
    }
};

复杂度

  • 时间复杂度O(n)。因为最坏情况下可能要遍历完整个数组才能找到是否有重复元素。
  • 空间复杂度O(n)。因为需要一个空白数组，这属于额外空间。

解法二：原地交换

思路

题目中有一个条件是长度为n的数组nums里的所有数字都在0~n-1之间。这个条件告诉我们数组中最大元素的大小必然是小于等于最大下标的。我们可以考虑不再创建额外数组，在原数组中，将每个元素，放置在以他作为下标的位置上。而一但发现该位置已经放置了和下标相等的元素，那就说明数组中出现了重复元素，重复的元素就是这个元素。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int findRepeatNumber(vector<int>& nums) {
        int i=0;    
        while(i<nums.size()){   // 开始遍历
            if(nums[i] == i){   // 如果索引和索引指向的数字相等，则移动指针
                i++;
                continue;
            }
            if(nums[nums[i]]==nums[i])  // 如果索引所指的元素和以此元素为索引的元素相等，则重复，返回该元素
                return nums[i];
            swap(nums[i],nums[nums[i]]);    // 交换索引所指的元素和与该元素作为索引时所指的元素（将该元素放到以他为索引的位置。）
        }
        return -1;
    }
};

复杂度

  • 时间复杂度O(n)。同理，最坏情况下依然需要将数组进行彻底的遍历
  • 空间复杂度O(1)。不需要额外数组，我们是在原数组上进行原地交换。